;	Copyright (c) 2003-2004 Arjan Bakker
;	
;	Permission is hereby granted, free of charge, to any person obtaining a copy of 
;	this software and associated documentation files (the "Software"), to deal in 
;	the Software without restriction, including without limitation the rights to 
;	use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of 
;	the Software, and to permit persons to whom the Software is furnished to do so, 
;	subject to the following conditions:
;	
;	The above copyright notice and this permission notice shall be included in all 
;	copies or substantial portions of the Software.
;	
;	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
;	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS 
;	FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR 
;	COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER 
;	IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 
;	CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

		MODULE	bitbuster

; File: bitbuster
;
;	The bitbuster module gives you depack support for data packed
;	using the bitbuster algorithm.
;
; FUNCTION NAMES:
;	The functions <depack> and <depack_raw> are MODULE local, which means you
;	have to add the prefix "bitbuster." to its name. This is to prevent possible
;	name clashes with functions from other libraries you might be using. 
;	However, if you define <MAKE_BITBUSTER_GLOBAL> then these functions will be
;	available without the "bitbuster." prefix as well.
;
; COPYRIGHT & CREDITS:
;	This module has been released by Arjan Bakker under the MIT License;
;	please see the top of the source file(s) for the full copyright statement.
	
; DEFINE:	MAKE_BITBUSTER_GLOBAL
;	Defining this will make all public functions that are normally only
;	available with the "bitbuster." prefix to also be available without
;	this prefix. See the introduction of <bitbuster> for more information.
 
; DEFINE:	BITBUSTER_OPTIMIZE_SPEED
;	Defining this will optimize the bitbuster depacker for speed, at the cost of
;	bigger code.


		IFDEF	BITBUSTER_OPTIMIZE_SPEED
; use macro's for getbit routines when optimizing bitbuster depacker for speed 
; (inlined code, no overhead by calls)
		
		; macro to get a bit from the bitstream
		; carry if bit is set, nocarry if bit is clear
		; must be entered with second registerset switched in!
		MACRO	GET_BIT_FROM_BITSTREAM
		add	a,a		; shift out new bit
		jp	nz,.done	; if remaining value isn't zere, we're done

		ld	a,(hl)		; get 8 bits from bitstream
		inc	hl		; increase source data address

		rla                     ; (bit 0 will be set!!!!)
.done:          
		ENDM

		ENDIF			; IFDEF	BITBUSTER_OPTIMIZE_SPEED
	
	
		IFNDEF	BITBUSTER_OPTIMIZE_SPEED
; use calls for getbit code when not optimizing	for speed

		; macro to get a bit from the bitstream
		; carry if bit is set, nocarry if bit is clear
		; must be entered with second registerset switched in!
		MACRO	GET_BIT_FROM_BITSTREAM
		call	get_bit_from_bitstream
		ENDM

		ENDIF			; IFNDEF BITBUSTER_OPTIMIZE_SPEED  
	
			
; FUNCTION:	depack
;	Depack a blob of data that was packed with Bitbuster.
;
; ENTRY:
;	HL - Address of packed data
;	DE - Address to depack to
;
; EXIT:
;	HL - Size of depacked data
;	A  - Number of blocks left to decompress
;	FZ - Last block has been decompressed
;	FNZ- Last block hasn't been decompressed
;
; MODIFIES:
;	#AF, BC, BC', DE, DE', HL, HL'#
;
depack:		EXPORT	bitbuster.depack
		IFDEF	MAKE_BITBUSTER_GLOBAL
@depack:	EXPORT	depack		
		ENDIF
		
		ld	a,(block_count)
		or	a
		jr	nz,depack_continue	; continue depacking a block if more blocks left
		
		ld	a,(hl)
		ld	(block_count),a		; store block count
		
		inc	hl			; move to size of first block
		ld	(block_start),hl	; store starting address of block
		
depack_continue:
		ld	hl,(block_start)	; load starting address of block 
		inc	hl
		inc	hl                      ; move over block size
		
		push	de
		call	depack_raw	
		
		ld	(block_start),hl	; store starting address of next chunk	
		pop	hl
		ex	de,hl
		OR	A,A
		SBC	HL,DE
		
		ld	a,(block_count)
		dec	a
		ld	(block_count),a         ; decrease number of blocks to decompress
		ret
		
; FUNCTION:	depack_raw
;	Depack data that was packed with Bitbuster.
;	Decompresses the RAW data, i.e. the data that is storead after the block
;	count and block size!
;
; ENTRY:
;	HL - Address of packed data
;	DE - Address to depack to
;
; EXIT:
;	HL - Address of first byte after compressed data
;	DE - Address of first byte after decompressed data
;
; MODIFIES:
;	#AF, BC, BC', DE, DE', HL, HL'#
;
depack_raw:	EXPORT	bitbuster.depack_raw
		IFDEF	MAKE_BITBUSTER_GLOBAL
@depack_raw:	EXPORT	depack_raw		
                ENDIF
                
                ld	a,128

depack_loop:    GET_BIT_FROM_BITSTREAM		; get compression type bit
		jp	c,output_compressed	; if set, we got lz77 compression
		ldi				; copy byte from compressed data to destination (literal byte)
	
		IFDEF	BITBUSTER_OPTIMIZE_SPEED
		GET_BIT_FROM_BITSTREAM		; get compression type bit
		jp	c,output_compressed	; if set, we got lz77 compression
		ldi				; copy byte from compressed data to destination (literal byte)
		GET_BIT_FROM_BITSTREAM		; get compression type bit
		jp	c,output_compressed	; if set, we got lz77 compression
		ldi				; copy byte from compressed data to destination (literal byte)
		ENDIF

		jp	depack_loop
	

;handle compressed data
output_compressed:
; calculate length value
		ld	bc,1
get_gamma_value:
	  	GET_BIT_FROM_BITSTREAM   	; get more bits
	  	jr 	nc,get_gamma_value_end
	  	GET_BIT_FROM_BITSTREAM   	; get next bit of value from bitstream
	  	rl	c
	  	rl	b
	  	jp 	nc,get_gamma_value  	; repeat unless overflow occurred (=end of block marker)
	  	ret
  	
get_gamma_value_end:
	  	inc 	bc  			; length was stored as length-2 so correct this

		ld	(source_length),bc

		ld	c,(hl)			; get lowest 7 bits of offset, plus offset extension bit
		inc	hl			; to next byte in compressed data
	  	
		ld	b,0
		bit	7,c
		jr	z,output_match1		; no need to get extra bits if carry not set
	
		GET_BIT_FROM_BITSTREAM		; get offset bit 10 
		rl	b
		GET_BIT_FROM_BITSTREAM		; get offset bit 9
		rl	b
		GET_BIT_FROM_BITSTREAM		; get offset bit 8
		rl	b
		GET_BIT_FROM_BITSTREAM		; get offset bit 7
	
		jp	c,output_match2		; since extension mark already makes bit 7 set
		res	7,c			; only clear it if the bit should be cleared
output_match1:  scf
output_match2:	push	hl			; address compressed data on stack

		ld	h,d
		ld	l,e			; destination address in HL...
		sbc	hl,bc			; calculate source address
			
		ld	bc,(source_length)
	
		ldir				; transfer data
	
		pop	hl			; address compressed data back from stack
	        
		IFDEF	BITBUSTER_OPTIMIZE_SPEED
		GET_BIT_FROM_BITSTREAM		; get compression type bit
		jp	c,output_compressed	; if set, we got lz77 compression
		ldi				; copy byte from compressed data to destination (literal byte)
		GET_BIT_FROM_BITSTREAM		; get compression type bit
		jp	c,output_compressed	; if set, we got lz77 compression
		ldi				; copy byte from compressed data to destination (literal byte)
		ENDIF
	
		jp	depack_loop
	
	
		IFNDEF	BITBUSTER_OPTIMIZE_SPEED

; get a bit from the bitstream
; carry if bit is set, nocarry if bit is clear
; must be entered with regular registerset switched in!
get_bit_from_bitstream:
		add	a,a		; shift out new bit
		ret	nz		; if remaining value isn't zere, we're done
	                                  
		ld	a,(hl)		; get 8 bits from bitstream
		inc	hl		; increase source data address
	
		rla                     ;(bit 0 will be set!!!!)
		ret
		ENDIF			; IFNDEF BITBUSTER_OPTIMIZE_SPEED
		
source_length:	dw	0		; length of source string
block_count:	db	0		; number of blocks to decompress
block_start:	dw	0               ; starting address of next block
	
	
		MODULE
		
